<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 2.3</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 2.3" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 2.3" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-2.xhtml#Chapter-2" rel="prev" title="Chapter 2" />
<link href="2_002e4.xhtml#g_t2_002e4" rel="next" title="2.4" />
<link href="2_002e2.xhtml#g_t2_002e2_002e4" rel="prev" title="2.2.4" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t2_002e3"></a>
<nav class="header">
<p>
Next: <a href="2_002e4.xhtml#g_t2_002e4" accesskey="n" rel="next">2.4</a>, Prev: <a href="2_002e2.xhtml#g_t2_002e2" accesskey="p" rel="prev">2.2</a>, Up: <a href="Chapter-2.xhtml#Chapter-2" accesskey="u" rel="prev">Chapter 2</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Symbolic-Data"></a>
<h3 class="section"><span class="secnum">2.3</span><span class="sectitle">Symbolic Data</span></h3>

<p>All the compound data objects we have used so far were constructed ultimately
from numbers.  In this section we extend the representational capability of our
language by introducing the ability to work with arbitrary symbols as data.
</p>

<a id="g_t2_002e3_002e1"></a>
<a id="Quotation"></a>
<h4 class="subsection"><span class="secnum">2.3.1</span><span class="sectitle">Quotation</span></h4>

<p>If we can form compound data using symbols, we can have lists such as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="lit">23</span><span class="pln"> </span><span class="lit">45</span><span class="pln"> </span><span class="lit">17</span><span class="clo">)</span><span class="pln">
</span><span class="opn">((</span><span class="pln">Norah </span><span class="lit">12</span><span class="clo">)</span><span class="pln"> 
 </span><span class="opn">(</span><span class="pln">Molly </span><span class="lit">9</span><span class="clo">)</span><span class="pln"> 
 </span><span class="opn">(</span><span class="pln">Anna </span><span class="lit">7</span><span class="clo">)</span><span class="pln"> 
 </span><span class="opn">(</span><span class="pln">Lauren </span><span class="lit">6</span><span class="clo">)</span><span class="pln"> 
 </span><span class="opn">(</span><span class="pln">Charlotte </span><span class="lit">4</span><span class="clo">))</span></pre></div>

<p>Lists containing symbols can look just like the expressions of our
language:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">23</span><span class="pln"> </span><span class="lit">45</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">9</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fact n</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> 
      </span><span class="lit">1</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> n </span><span class="opn">(</span><span class="pln">fact </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>In order to manipulate symbols we need a new element in our language: the
ability to <a id="index-quote"></a>
<em>quote</em> a data object.  Suppose we want to construct the
list <code>(a b)</code>.  We can’t accomplish this with <code>(list a b)</code>, because
this expression constructs a list of the <a id="index-values"></a>
<em>values</em> of <code>a</code> and
<code>b</code> rather than the symbols themselves.  This issue is well known in the
context of natural languages, where words and sentences may be regarded either
as semantic entities or as character strings (syntactic entities).  The common
practice in natural languages is to use quotation marks to indicate that a word
or a sentence is to be treated literally as a string of characters.  For
instance, the first letter of “John” is clearly “J.”  If we tell somebody
“say your name aloud,” we expect to hear that person’s name.  However, if we
tell somebody “say ‘your name’ aloud,” we expect to hear the words “your
name.”  Note that we are forced to nest quotation marks to describe what
somebody else might say.<a class="footnote_link" id="DOCF98" href="#FOOT98"><sup>98</sup></a>
</p>
<p>We can follow this same practice to identify lists and symbols that are to be
treated as data objects rather than as expressions to be evaluated.  However,
our format for quoting differs from that of natural languages in that we place
a quotation mark (traditionally, the single quote symbol <code>'</code>)<!-- /@w --> only at the
beginning of the object to be quoted.  We can get away with this in Scheme
syntax because we rely on blanks and parentheses to delimit objects.  Thus, the
meaning of the single quote character is to quote the next object.<a class="footnote_link" id="DOCF99" href="#FOOT99"><sup>99</sup></a>
</p>
<p>Now we can distinguish between symbols and their values:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> a </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> b </span><span class="lit">2</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="pln">list a b</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">list </span><span class="lit">'a</span><span class="pln"> </span><span class="lit">'b</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="pln">a b</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">list </span><span class="lit">'a</span><span class="pln"> b</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="pln">a </span><span class="lit">2</span><span class="clo">)</span></i>
</pre></div>

<p>Quotation also allows us to type in compound objects, using the conventional
printed representation for lists:<a class="footnote_link" id="DOCF100" href="#FOOT100"><sup>100</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">a b c</span><span class="clo">))</span><span class="pln">
</span><i><span class="pln">a</span></i><span class="pln">

</span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">a b c</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="pln">b c</span><span class="clo">)</span></i>
</pre></div>

<p>In keeping with this, we can obtain the empty list by evaluating <code>'()</code>,
and thus dispense with the variable <code>nil</code>.
</p>
<p>One additional primitive used in manipulating symbols is <code>eq?</code>, which
takes two symbols as arguments and tests whether they are the same.<a class="footnote_link" id="DOCF101" href="#FOOT101"><sup>101</sup></a>
Using <code>eq?</code>, we can implement a useful procedure called <code>memq</code>.  This
takes two arguments, a symbol and a list.  If the symbol is not contained in
the list (i.e., is not <code>eq?</code> to any item in the list), then <code>memq</code>
returns false.  Otherwise, it returns the sublist of the list beginning with
the first occurrence of the symbol:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">memq item x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? x</span><span class="clo">)</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> item </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">))</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">memq item </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">)))))</span></pre></div>

<p>For example, the value of
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">memq </span><span class="lit">'apple</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">pear banana prune</span><span class="clo">))</span></pre></div>

<p>is false, whereas the value of
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">memq </span><span class="lit">'apple</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">x </span><span class="opn">(</span><span class="pln">apple sauce</span><span class="clo">)</span><span class="pln"> y apple pear</span><span class="clo">))</span></pre></div>

<p>is <code>(apple pear)</code>.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e53"></a>Exercise 2.53:</strong> What would the interpreter print
in response to evaluating each of the following expressions?
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">list </span><span class="lit">'a</span><span class="pln"> </span><span class="lit">'b</span><span class="pln"> </span><span class="lit">'c</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'george</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="pln">x1 x2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y1 y2</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="pln">x1 x2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y1 y2</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">pair? </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">a short list</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">memq </span><span class="lit">'red</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="pln">red shoes</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">blue socks</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">memq </span><span class="lit">'red</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">red shoes blue socks</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e54"></a>Exercise 2.54:</strong> Two lists are said to be
<code>equal?</code> if they contain equal elements arranged in the same order.  For
example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">equal</span><span class="pun">?</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">this is a list</span><span class="clo">)</span><span class="pln"> 
        </span><span class="lit">'</span><span class="opn">(</span><span class="pln">this is a list</span><span class="clo">))</span></pre></div>

<p>is true, but
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">equal</span><span class="pun">?</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">this is a list</span><span class="clo">)</span><span class="pln"> 
        </span><span class="lit">'</span><span class="opn">(</span><span class="pln">this </span><span class="opn">(</span><span class="pln">is a</span><span class="clo">)</span><span class="pln"> list</span><span class="clo">))</span></pre></div>

<p>is false.  To be more precise, we can define <code>equal?</code>  recursively in
terms of the basic <code>eq?</code> equality of symbols by saying that <code>a</code> and
<code>b</code> are <code>equal?</code> if they are both symbols and the symbols are
<code>eq?</code>, or if they are both lists such that <code>(car a)</code> is <code>equal?</code>
to <code>(car b)</code> and <code>(cdr a)</code> is <code>equal?</code> to <code>(cdr b)</code>.  Using
this idea, implement <code>equal?</code> as a procedure.<a class="footnote_link" id="DOCF102" href="#FOOT102"><sup>102</sup></a>
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e55"></a>Exercise 2.55:</strong> Eva Lu Ator types to the
interpreter the expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="lit">''abracadabra</span><span class="clo">)</span></pre></div>

<p>To her surprise, the interpreter prints back <code>quote</code>.  Explain.
</p></blockquote>

<a id="g_t2_002e3_002e2"></a>
<a id="Example_003a-Symbolic-Differentiation"></a>
<h4 class="subsection"><span class="secnum">2.3.2</span><span class="sectitle">Example: Symbolic Differentiation</span></h4>

<p>As an illustration of symbol manipulation and a further illustration of data
abstraction, consider the design of a procedure that performs symbolic
differentiation of algebraic expressions.  We would like the procedure to take
as arguments an algebraic expression and a variable and to return the
derivative of the expression with respect to the variable.  For example, if the
arguments to the procedure are <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mi>b</mi>
    <mi>x</mi>
    <mo>+</mo>
    <mi>c</mi>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>, the
procedure should return <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <mi>a</mi>
    <mi>x</mi>
    <mo>+</mo>
    <mi>b</mi>
  </mrow>
</math>.  Symbolic differentiation is of
special historical significance in Lisp.  It was one of the motivating examples
behind the development of a computer language for symbol manipulation.
Furthermore, it marked the beginning of the line of research that led to the
development of powerful systems for symbolic mathematical work, which are
currently being used by a growing number of applied mathematicians and
physicists.
</p>
<p>In developing the symbolic-differentiation program, we will follow the same
strategy of data abstraction that we followed in developing the rational-number
system of <a href="2_002e1.xhtml#g_t2_002e1_002e1">2.1.1</a>.  That is, we will first define a differentiation
algorithm that operates on abstract objects such as “sums,” “products,” and
“variables” without worrying about how these are to be represented.  Only
afterward will we address the representation problem.
</p>
<a id="The-differentiation-program-with-abstract-data"></a>
<h5 class="subsubheading">The differentiation program with abstract data</h5>

<p>In order to keep things simple, we will consider a very simple
symbolic-differentiation program that handles expressions that are built up
using only the operations of addition and multiplication with two arguments.
Differentiation of any such expression can be carried out by applying the
following reduction rules:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mrow>
          <mi>d</mi>
          <mi>c</mi>
        </mrow>
        <mrow>
          <mi>d</mi>
          <mi>x</mi>
        </mrow>
      </mfrac>
    </mrow>
    <mspace width="thinmathspace"/>
    <mo>=</mo>
    <mspace width="thinmathspace"/>
    <mn>0</mn>
    <mo>,</mo>
  </mrow>
  <mspace width="1em"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>for </mtext>
    <mi>c</mi>
    <mtext> a constant </mtext>
  </mrow>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>or a variable </mtext>
  </mrow>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>different from </mtext>
    <mi>x</mi>
    <mo>,</mo>
  </mrow>
</math>
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right center left" rowspacing="3pt" columnspacing="thickmathspace">
    <mtr>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <mi>x</mi>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>x</mi>
            </mrow>
          </mfrac>
        </mrow>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mn>1</mn>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <mo stretchy="false">(</mo>
              <mi>u</mi>
              <mo>+</mo>
              <mi>v</mi>
              <mo stretchy="false">)</mo>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>x</mi>
            </mrow>
          </mfrac>
        </mrow>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <mi>u</mi>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>x</mi>
            </mrow>
          </mfrac>
        </mrow>
        <mo>+</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <mi>v</mi>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>x</mi>
            </mrow>
          </mfrac>
        </mrow>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <mo stretchy="false">(</mo>
              <mi>u</mi>
              <mi>v</mi>
              <mo stretchy="false">)</mo>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>x</mi>
            </mrow>
          </mfrac>
        </mrow>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mi>u</mi>
        <mspace width="0.1em"/>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <mi>v</mi>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>x</mi>
            </mrow>
          </mfrac>
        </mrow>
        <mo>+</mo>
        <mi>v</mi>
        <mspace width="0.1em"/>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <mi>u</mi>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>x</mi>
            </mrow>
          </mfrac>
        </mrow>
        <mo>.</mo>
      </mtd>
    </mtr>
  </mtable>
</math>
Observe that the latter two rules are recursive in nature.  That is, to obtain
the derivative of a sum we first find the derivatives of the terms and add
them.  Each of the terms may in turn be an expression that needs to be
decomposed.  Decomposing into smaller and smaller pieces will eventually
produce pieces that are either constants or variables, whose derivatives will
be either 0 or 1.
</p>
<p>To embody these rules in a procedure we indulge in a little wishful thinking,
as we did in designing the rational-number implementation.  If we had a means
for representing algebraic expressions, we should be able to tell whether an
expression is a sum, a product, a constant, or a variable.  We should be able
to extract the parts of an expression.  For a sum, for example we want to be
able to extract the addend (first term) and the augend (second term).  We
should also be able to construct expressions from parts.  Let us assume that we
already have procedures to implement the following selectors, constructors, and
predicates:
</p>
<div class="example">
<pre class="example">(variable? e)          <span class="roman">Is <code>e</code> a variable?</span>
(same-variable? v1 v2) <span class="roman">Are <code>v1</code> and <code>v2</code> the same variable?</span>
(sum? e)               <span class="roman">Is <code>e</code> a sum?</span>
(addend e)             <span class="roman">Addend of the sum <code>e</code>.</span>
(augend e)             <span class="roman">Augend of the sum <code>e</code>.</span>
(make-sum a1 a2)       <span class="roman">Construct the sum of <code>a1</code> and <code>a2</code>.</span>
(product? e)           <span class="roman">Is <code>e</code> a product?</span>
(multiplier e)         <span class="roman">Multiplier of the product <code>e</code>.</span>
(multiplicand e)       <span class="roman">Multiplicand of the product <code>e</code>.</span>
(make-product m1 m2)   <span class="roman">Construct the product of <code>m1</code> and <code>m2</code>.</span>
</pre></div>

<p>Using these, and the primitive predicate <code>number?</code>, which identifies
numbers, we can express the differentiation rules as the following procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deriv exp var</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">number? exp</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">variable? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">same-variable? exp var</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">sum? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-sum </span><span class="opn">(</span><span class="pln">deriv </span><span class="opn">(</span><span class="pln">addend exp</span><span class="clo">)</span><span class="pln"> var</span><span class="clo">)</span><span class="pln">
                   </span><span class="opn">(</span><span class="pln">deriv </span><span class="opn">(</span><span class="pln">augend exp</span><span class="clo">)</span><span class="pln"> var</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">product? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-sum
          </span><span class="opn">(</span><span class="pln">make-product 
           </span><span class="opn">(</span><span class="pln">multiplier exp</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">deriv </span><span class="opn">(</span><span class="pln">multiplicand exp</span><span class="clo">)</span><span class="pln"> var</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">make-product 
           </span><span class="opn">(</span><span class="pln">deriv </span><span class="opn">(</span><span class="pln">multiplier exp</span><span class="clo">)</span><span class="pln"> var</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">multiplicand exp</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"unknown expression 
                      type: DERIV"</span><span class="pln"> exp</span><span class="clo">))))</span></pre></div>

<p>This <code>deriv</code> procedure incorporates the complete differentiation
algorithm.  Since it is expressed in terms of abstract data, it will work no
matter how we choose to represent algebraic expressions, as long as we design a
proper set of selectors and constructors.  This is the issue we must address
next.
</p>
<a id="Representing-algebraic-expressions"></a>
<h5 class="subsubheading">Representing algebraic expressions</h5>

<p>We can imagine many ways to use list structure to represent algebraic
expressions.  For example, we could use lists of symbols that mirror the usual
algebraic notation, representing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mi>x</mi>
    <mo>+</mo>
    <mi>b</mi>
  </mrow>
</math> as the list <code>(a * x + b)</code>.  
However, one especially straightforward choice is to use the same
parenthesized prefix notation that Lisp uses for combinations; that is, to
represent <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mi>x</mi>
    <mo>+</mo>
    <mi>b</mi>
  </mrow>
</math> as <code>(+ (* a x) b)</code>.  Then our data
representation for the differentiation problem is as follows:
</p>
<ul>
<li> The variables are symbols.  They are identified by the primitive predicate
<code>symbol?</code>:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">variable? x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? x</span><span class="clo">))</span></pre></div>

</li><li> Two variables are the same if the symbols representing them are <code>eq?</code>:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">same-variable? v1 v2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">variable? v1</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">variable? v2</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> v1 v2</span><span class="clo">)))</span></pre></div>

</li><li> Sums and products are constructed as lists:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-sum a1 a2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'</span><span class="pun">+</span><span class="pln"> a1 a2</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-product m1 m2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'</span><span class="pun">*</span><span class="pln"> m1 m2</span><span class="clo">))</span></pre></div>

</li><li> A sum is a list whose first element is the symbol <code>+</code>:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum? x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="pun">+</span><span class="clo">)))</span></pre></div>

</li><li> The addend is the second item of the sum list:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">addend s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> s</span><span class="clo">))</span></pre></div>

</li><li> The augend is the third item of the sum list:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">augend s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> s</span><span class="clo">))</span></pre></div>

</li><li> A product is a list whose first element is the symbol <code>*</code>:
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">product? x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="pun">*</span><span class="clo">)))</span></pre></div>

</li><li> The multiplier is the second item of the product list:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">multiplier p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> p</span><span class="clo">))</span></pre></div>

</li><li> The multiplicand is the third item of the product list:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">multiplicand p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> p</span><span class="clo">))</span></pre></div>

</li></ul>

<p>Thus, we need only combine these with the algorithm as embodied by <code>deriv</code>
in order to have a working symbolic-differentiation program.  Let us look at
some examples of its behavior:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">deriv </span><span class="lit">'</span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">3</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'x</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">deriv </span><span class="lit">'</span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'x</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> y</span><span class="clo">))</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">deriv </span><span class="lit">'</span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">3</span><span class="clo">))</span><span class="pln"> </span><span class="lit">'x</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span></i><span class="pln">
   </span><i><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> y</span><span class="clo">))</span></i><span class="pln">
      </span><i><span class="opn">(</span><span class="pun">+</span><span class="pln">  x </span><span class="lit">3</span><span class="clo">)))</span></i>
</pre></div>

<p>The program produces answers that are correct; however, they are unsimplified.
It is true that
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mrow>
        <mi>d</mi>
        <mo stretchy="false">(</mo>
        <mi>x</mi>
        <mi>y</mi>
        <mo stretchy="false">)</mo>
      </mrow>
      <mrow>
        <mi>d</mi>
        <mi>x</mi>
      </mrow>
    </mfrac>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mn>0</mn>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>⋅<!-- ⋅ --></mo>
    <mi>y</mi>
    <mo>,</mo>
  </mrow>
</math>
but we would like the program to know that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mn>0</mn>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>⋅<!-- ⋅ --></mo>
    <mi>y</mi>
    <mo>=</mo>
    <mi>y</mi>
  </mrow>
</math>,
and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>0</mn>
    <mo>+</mo>
    <mi>y</mi>
    <mo>=</mo>
    <mi>y</mi>
  </mrow>
</math>.  The answer for the second example should have been
simply <code>y</code>.  As the third example shows, this becomes a serious issue when
the expressions are complex.
</p>
<p>Our difficulty is much like the one we encountered with the rational-number
implementation: we haven’t reduced answers to simplest form.  To accomplish the
rational-number reduction, we needed to change only the constructors and the
selectors of the implementation.  We can adopt a similar strategy here.  We
won’t change <code>deriv</code> at all.  Instead, we will change <code>make-sum</code> so
that if both summands are numbers, <code>make-sum</code> will add them and return
their sum.  Also, if one of the summands is 0, then <code>make-sum</code> will return
the other summand:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-sum a1 a2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln">number? a1 </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> a2</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln">number? a2 </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> a1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">number? a1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">number? a2</span><span class="clo">))</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a1 a2</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'</span><span class="pun">+</span><span class="pln"> a1 a2</span><span class="clo">))))</span></pre></div>

<p>This uses the procedure <code>=number?</code>, which checks whether an expression is
equal to a given number:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln">number? exp num</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">number? exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> exp num</span><span class="clo">)))</span></pre></div>

<p>Similarly, we will change <code>make-product</code> to build in the rules that 0
times anything is 0 and 1 times anything is the thing itself:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-product m1 m2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln">number? m1 </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pun">=</span><span class="pln">number? m2 </span><span class="lit">0</span><span class="clo">))</span><span class="pln"> 
         </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln">number? m1 </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> m2</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln">number? m2 </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> m1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">number? m1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">number? m2</span><span class="clo">))</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> m1 m2</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'</span><span class="pun">*</span><span class="pln"> m1 m2</span><span class="clo">))))</span></pre></div>

<p>Here is how this version works on our three examples:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">deriv </span><span class="lit">'</span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">3</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'x</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">1</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">deriv </span><span class="lit">'</span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'x</span><span class="clo">)</span><span class="pln">
</span><i><span class="pln">y</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">deriv </span><span class="lit">'</span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">3</span><span class="clo">))</span><span class="pln"> </span><span class="lit">'x</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> y </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">3</span><span class="clo">)))</span></i>
</pre></div>

<p>Although this is quite an improvement, the third example shows that there is
still a long way to go before we get a program that puts expressions into a
form that we might agree is “simplest.”  The problem of algebraic
simplification is complex because, among other reasons, a form that may be
simplest for one purpose may not be for another.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e56"></a>Exercise 2.56:</strong> Show how to extend the basic
differentiator to handle more kinds of expressions.  For instance, implement
the differentiation rule
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mrow>
        <mi>d</mi>
        <mo stretchy="false">(</mo>
        <msup>
          <mi>u</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mspace width="0.1ex"/>
            <mi>n</mi>
          </mrow>
        </msup>
        <mo stretchy="false">)</mo>
      </mrow>
      <mrow>
        <mi>d</mi>
        <mi>x</mi>
      </mrow>
    </mfrac>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <msup>
      <mi>u</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mspace width="0.1ex"/>
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msup>
    <mspace width="thinmathspace"/>
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mrow>
          <mi>d</mi>
          <mi>u</mi>
        </mrow>
        <mrow>
          <mi>d</mi>
          <mi>x</mi>
        </mrow>
      </mfrac>
    </mrow>
  </mrow>
</math>
by adding a new clause to the <code>deriv</code> program and defining appropriate
procedures <code>exponentiation?</code>, <code>base</code>, <code>exponent</code>, and
<code>make-exponentiation</code>.  (You may use the symbol <code>**</code> to denote
exponentiation.)  Build in the rules that anything raised to the power 0 is 1
and anything raised to the power 1 is the thing itself.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e57"></a>Exercise 2.57:</strong> Extend the differentiation
program to handle sums and products of arbitrary numbers of (two or more)
terms.  Then the last example above could be expressed as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">deriv </span><span class="lit">'</span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">3</span><span class="clo">))</span><span class="pln"> </span><span class="lit">'x</span><span class="clo">)</span></pre></div>

<p>Try to do this by changing only the representation for sums and products,
without changing the <code>deriv</code> procedure at all.  For example, the
<code>addend</code> of a sum would be the first term, and the <code>augend</code> would be
the sum of the rest of the terms.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e58"></a>Exercise 2.58:</strong> Suppose we want to modify the
differentiation program so that it works with ordinary mathematical notation,
in which <code>+</code> and <code>*</code> are infix rather than prefix operators.  Since
the differentiation program is defined in terms of abstract data, we can modify
it to work with different representations of expressions solely by changing the
predicates, selectors, and constructors that define the representation of the
algebraic expressions on which the differentiator is to operate.
</p>
<ol>
<li> Show how to do this in order to differentiate algebraic expressions presented
in infix form, such as <code>(x + (3 * (x + (y + 2))))</code>.  To simplify the task,
assume that <code>+</code> and <code>*</code> always take two arguments and that
expressions are fully parenthesized.

</li><li> The problem becomes substantially harder if we allow standard algebraic
notation, such as <code>(x + 3 * (x + y + 2))</code>, which drops unnecessary
parentheses and assumes that multiplication is done before addition.  Can you
design appropriate predicates, selectors, and constructors for this notation
such that our derivative program still works?

</li></ol>
</blockquote>

<a id="g_t2_002e3_002e3"></a>
<a id="Example_003a-Representing-Sets"></a>
<h4 class="subsection"><span class="secnum">2.3.3</span><span class="sectitle">Example: Representing Sets</span></h4>

<p>In the previous examples we built representations for two kinds of compound
data objects: rational numbers and algebraic expressions.  In one of these
examples we had the choice of simplifying (reducing) the expressions at either
construction time or selection time, but other than that the choice of a
representation for these structures in terms of lists was straightforward. When
we turn to the representation of sets, the choice of a representation is not so
obvious.  Indeed, there are a number of possible representations, and they
differ significantly from one another in several ways.
</p>
<p>Informally, a set is simply a collection of distinct objects.  To give a more
precise definition we can employ the method of data abstraction.  That is, we
define “set” by specifying the operations that are to be used on sets.  These
are <code>union-set</code>, <code>intersection-set</code>, <code>element-of-set?</code>, and
<code>adjoin-set</code>.  <code>Element-of-set?</code> is a predicate that determines
whether a given element is a member of a set.  <code>Adjoin-set</code> takes an
object and a set as arguments and returns a set that contains the elements of
the original set and also the adjoined element.  <code>Union-set</code> computes the
union of two sets, which is the set containing each element that appears in
either argument.  <code>Intersection-set</code> computes the intersection of two
sets, which is the set containing only elements that appear in both arguments.
From the viewpoint of data abstraction, we are free to design any
representation that implements these operations in a way consistent with the
interpretations given above.<a class="footnote_link" id="DOCF103" href="#FOOT103"><sup>103</sup></a>
</p>
<a id="Sets-as-unordered-lists"></a>
<h5 class="subsubheading">Sets as unordered lists</h5>

<p>One way to represent a set is as a list of its elements in which no element
appears more than once.  The empty set is represented by the empty list.  In
this representation, <code>element-of-set?</code> is similar to the procedure
<code>memq</code> of <a href="#g_t2_002e3_002e1">2.3.1</a>.  It uses <code>equal?</code>  instead of
<code>eq?</code> so that the set elements need not be symbols:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">element-of-set? x </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? </span><span class="kwd">set</span><span class="clo">)</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">equal</span><span class="pun">?</span><span class="pln"> x </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">))</span><span class="pln"> true</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">element-of-set? x </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">)))))</span></pre></div>

<p>Using this, we can write <code>adjoin-set</code>.  If the object to be adjoined is
already in the set, we just return the set.  Otherwise, we use <code>cons</code> to
add the object to the list that represents the set:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">adjoin-set x </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">element-of-set? x </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
      </span><span class="kwd">set</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x </span><span class="kwd">set</span><span class="clo">)))</span></pre></div>

<p>For <code>intersection-set</code> we can use a recursive strategy.  If we know how to
form the intersection of <code>set2</code> and the <code>cdr</code> of <code>set1</code>, we only
need to decide whether to include the <code>car</code> of <code>set1</code> in this.  But
this depends on whether <code>(car set1)</code> is also in <code>set2</code>.  Here is the
resulting procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">intersection-set set1 set2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? set1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? set2</span><span class="clo">))</span><span class="pln"> 
         </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">element-of-set? </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> set1</span><span class="clo">)</span><span class="pln"> set2</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> set1</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">intersection-set </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> set1</span><span class="clo">)</span><span class="pln"> 
                                 set2</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">intersection-set </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> set1</span><span class="clo">)</span><span class="pln"> 
                                set2</span><span class="clo">))))</span></pre></div>

<p>In designing a representation, one of the issues we should be concerned with is
efficiency.  Consider the number of steps required by our set operations.
Since they all use <code>element-of-set?</code>, the speed of this operation has a
major impact on the efficiency of the set implementation as a whole.  Now, in
order to check whether an object is a member of a set, <code>element-of-set?</code>
may have to scan the entire set. (In the worst case, the object turns out not
to be in the set.)  Hence, if the set has <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> elements,
<code>element-of-set?</code>  might take up to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> steps.  Thus, the number of
steps required grows as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  The number of steps required by
<code>adjoin-set</code>, which uses this operation, also grows as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.
For <code>intersection-set</code>, which does an <code>element-of-set?</code> check for
each element of <code>set1</code>, the number of steps required grows as the product
of the sizes of the sets involved, or <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
    <mo stretchy="false">)</mo>
  </mrow>
</math> for two sets of size
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  The same will be true of <code>union-set</code>.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e59"></a>Exercise 2.59:</strong> Implement the <code>union-set</code>
operation for the unordered-list representation of sets.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e60"></a>Exercise 2.60:</strong> We specified that a set would be
represented as a list with no duplicates.  Now suppose we allow duplicates.
For instance, the set <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>2</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math> could be represented as the list <code>(2 3 2 1
3 2 2)</code>.  Design procedures <code>element-of-set?</code>, <code>adjoin-set</code>,
<code>union-set</code>, and <code>intersection-set</code> that operate on this
representation.  How does the efficiency of each compare with the corresponding
procedure for the non-duplicate representation?  Are there applications for
which you would use this representation in preference to the non-duplicate one?
</p></blockquote>

<a id="Sets-as-ordered-lists"></a>
<h5 class="subsubheading">Sets as ordered lists</h5>

<p>One way to speed up our set operations is to change the representation so that
the set elements are listed in increasing order.  To do this, we need some way
to compare two objects so that we can say which is bigger.  For example, we
could compare symbols lexicographically, or we could agree on some method for
assigning a unique number to an object and then compare the elements by
comparing the corresponding numbers.  To keep our discussion simple, we will
consider only the case where the set elements are numbers, so that we can
compare elements using <code>&gt;</code> and <code>&lt;</code>.  We will represent a set of
numbers by listing its elements in increasing order.  Whereas our first
representation above allowed us to represent the set <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo>,</mo>
    <mn>6</mn>
    <mo>,</mo>
    <mn>10</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math> by listing
the elements in any order, our new representation allows only the list <code>(1
3 6 10)</code>.
</p>
<p>One advantage of ordering shows up in <code>element-of-set?</code>: In checking for
the presence of an item, we no longer have to scan the entire set.  If we reach
a set element that is larger than the item we are looking for, then we know
that the item is not in the set:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">element-of-set? x </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? </span><span class="kwd">set</span><span class="clo">)</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> x </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">))</span><span class="pln"> true</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">&lt;</span><span class="pln"> x </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">))</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">element-of-set? x </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">)))))</span></pre></div>

<p>How many steps does this save?  In the worst case, the item we are looking for
may be the largest one in the set, so the number of steps is the same as for
the unordered representation.  On the other hand, if we search for items of
many different sizes we can expect that sometimes we will be able to stop
searching at a point near the beginning of the list and that other times we
will still need to examine most of the list.  On the average we should expect
to have to examine about half of the items in the set.  Thus, the average
number of steps required will be about <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mn>2</mn>
  </mrow>
</math>.  This is still
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> growth, but it does save us, on the average, a factor of 2
in number of steps over the previous implementation.
</p>
<p>We obtain a more impressive speedup with <code>intersection-set</code>.  In the
unordered representation this operation required <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
    <mo stretchy="false">)</mo>
  </mrow>
</math> steps,
because we performed a complete scan of <code>set2</code> for each element of
<code>set1</code>.  But with the ordered representation, we can use a more clever
method.  Begin by comparing the initial elements, <code>x1</code> and <code>x2</code>, of
the two sets.  If <code>x1</code> equals <code>x2</code>, then that gives an element of the
intersection, and the rest of the intersection is the intersection of the
<code>cdr</code>-s of the two sets.  Suppose, however, that <code>x1</code> is less than
<code>x2</code>.  Since <code>x2</code> is the smallest element in <code>set2</code>, we can
immediately conclude that <code>x1</code> cannot appear anywhere in <code>set2</code> and
hence is not in the intersection.  Hence, the intersection is equal to the
intersection of <code>set2</code> with the <code>cdr</code> of <code>set1</code>.  Similarly, if
<code>x2</code> is less than <code>x1</code>, then the intersection is given by the
intersection of <code>set1</code> with the <code>cdr</code> of <code>set2</code>.  Here is the
procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">intersection-set set1 set2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? set1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? set2</span><span class="clo">))</span><span class="pln">
      </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x1 </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> set1</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x2 </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> set2</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> x1 x2</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x1 </span><span class="opn">(</span><span class="pln">intersection-set 
                         </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> set1</span><span class="clo">)</span><span class="pln">
                         </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> set2</span><span class="clo">))))</span><span class="pln">
              </span><span class="opn">((</span><span class="pun">&lt;</span><span class="pln"> x1 x2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">intersection-set 
                          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> set1</span><span class="clo">)</span><span class="pln"> 
                          set2</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">((</span><span class="pun">&lt;</span><span class="pln"> x2 x1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">intersection-set 
                          set1 
                          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> set2</span><span class="clo">)))))))</span></pre></div>

<p>To estimate the number of steps required by this process, observe that at each
step we reduce the intersection problem to computing intersections of smaller
sets—removing the first element from <code>set1</code> or <code>set2</code> or both.
Thus, the number of steps required is at most the sum of the sizes of
<code>set1</code> and <code>set2</code>, rather than the product of the sizes as with the
unordered representation.  This is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> growth rather than
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
    <mo stretchy="false">)</mo>
  </mrow>
</math>—a considerable speedup, even for sets of moderate size.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e61"></a>Exercise 2.61:</strong> Give an implementation of
<code>adjoin-set</code> using the ordered representation.  By analogy with
<code>element-of-set?</code> show how to take advantage of the ordering to produce a
procedure that requires on the average about half as many steps as with the
unordered representation.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e62"></a>Exercise 2.62:</strong> Give a <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>
implementation of <code>union-set</code> for sets represented as ordered lists.
</p></blockquote>

<a id="Sets-as-binary-trees"></a>
<h5 class="subsubheading">Sets as binary trees</h5>

<p>We can do better than the ordered-list representation by arranging the set
elements in the form of a tree.  Each node of the tree holds one element of the
set, called the “entry” at that node, and a link to each of two other
(possibly empty) nodes.  The “left” link points to elements smaller than the
one at the node, and the “right” link to elements greater than the one at the
node.  <a href="#Figure-2_002e16">Figure 2.16</a> shows some trees that represent the set
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo>,</mo>
    <mn>5</mn>
    <mo>,</mo>
    <mn>7</mn>
    <mo>,</mo>
    <mn>9</mn>
    <mo>,</mo>
    <mn>11</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math>.  The same set may be represented by a tree in a number of
different ways.  The only thing we require for a valid representation is that
all elements in the left subtree be smaller than the node entry and that all
elements in the right subtree be larger.
</p>
<figure class="float">
<a id="Figure-2_002e16"></a>
<object style="width: 45.93ex; height: 21.50ex;" data="fig/chap2/Fig2.16c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.16:</strong> Various binary trees that represent the set <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo>,</mo>
    <mn>5</mn>
    <mo>,</mo>
    <mn>7</mn>
    <mo>,</mo>
    <mn>9</mn>
    <mo>,</mo>
    <mn>11</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math>.</p>
</figcaption>
</figure>

<p>The advantage of the tree representation is this: Suppose we want to check
whether a number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is contained in a set.  We begin by comparing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> with
the entry in the top node.  If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is less than this, we know that we need
only search the left subtree; if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is greater, we need only search the
right subtree.  Now, if the tree is “balanced,” each of these subtrees will
be about half the size of the original.  Thus, in one step we have reduced the
problem of searching a tree of size <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> to searching a tree of size <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mn>2</mn>
  </mrow>
</math>.
Since the size of the tree is halved at each step, we should expect that the
number of steps needed to search a tree of size <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> grows as
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.<a class="footnote_link" id="DOCF104" href="#FOOT104"><sup>104</sup></a> For large sets, this will be a
significant speedup over the previous representations.
</p>
<p>We can represent trees by using lists.  Each node will be a list of three
items: the entry at the node, the left subtree, and the right subtree.  A left
or a right subtree of the empty list will indicate that there is no subtree
connected there.  We can describe this representation by the following
procedures:<a class="footnote_link" id="DOCF105" href="#FOOT105"><sup>105</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">entry tree</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">left-branch tree</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">right-branch tree</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-tree entry left right</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list entry left right</span><span class="clo">))</span></pre></div>

<p>Now we can write the <code>element-of-set?</code> procedure using the strategy
described above:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">element-of-set? x </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? </span><span class="kwd">set</span><span class="clo">)</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">entry </span><span class="kwd">set</span><span class="clo">))</span><span class="pln"> true</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">&lt;</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">entry </span><span class="kwd">set</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">element-of-set? 
          x 
          </span><span class="opn">(</span><span class="pln">left-branch </span><span class="kwd">set</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">&gt;</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">entry </span><span class="kwd">set</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">element-of-set? 
          x 
          </span><span class="opn">(</span><span class="pln">right-branch </span><span class="kwd">set</span><span class="clo">)))))</span></pre></div>

<p>Adjoining an item to a set is implemented similarly and also requires
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> steps.  To adjoin an item <code>x</code>, we compare
<code>x</code> with the node entry to determine whether <code>x</code> should be added to
the right or to the left branch, and having adjoined <code>x</code> to the
appropriate branch we piece this newly constructed branch together with the
original entry and the other branch.  If <code>x</code> is equal to the entry, we
just return the node.  If we are asked to adjoin <code>x</code> to an empty tree, we
generate a tree that has <code>x</code> as the entry and empty right and left
branches.  Here is the procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">adjoin-set x </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? </span><span class="kwd">set</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-tree x </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">entry </span><span class="kwd">set</span><span class="clo">))</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">&lt;</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">entry </span><span class="kwd">set</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-tree 
          </span><span class="opn">(</span><span class="pln">entry </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">adjoin-set x </span><span class="opn">(</span><span class="pln">left-branch </span><span class="kwd">set</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">right-branch </span><span class="kwd">set</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">&gt;</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">entry </span><span class="kwd">set</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-tree
          </span><span class="opn">(</span><span class="pln">entry </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">left-branch </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">adjoin-set x </span><span class="opn">(</span><span class="pln">right-branch </span><span class="kwd">set</span><span class="clo">))))))</span></pre></div>

<p>The above claim that searching the tree can be performed in a logarithmic
number of steps rests on the assumption that the tree is “balanced,” i.e.,
that the left and the right subtree of every tree have approximately the same
number of elements, so that each subtree contains about half the elements of
its parent.  But how can we be certain that the trees we construct will be
balanced?  Even if we start with a balanced tree, adding elements with
<code>adjoin-set</code> may produce an unbalanced result.  Since the position of a
newly adjoined element depends on how the element compares with the items
already in the set, we can expect that if we add elements “randomly” the tree
will tend to be balanced on the average.  But this is not a guarantee.  For
example, if we start with an empty set and adjoin the numbers 1 through 7 in
sequence we end up with the highly unbalanced tree shown in <a href="#Figure-2_002e17">Figure 2.17</a>.
In this tree all the left subtrees are empty, so it has no advantage over a
simple ordered list.  One way to solve this problem is to define an operation
that transforms an arbitrary tree into a balanced tree with the same elements.
Then we can perform this transformation after every few <code>adjoin-set</code>
operations to keep our set in balance.  There are also other ways to solve this
problem, most of which involve designing new data structures for which
searching and insertion both can be done in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>
steps.<a class="footnote_link" id="DOCF106" href="#FOOT106"><sup>106</sup></a>
</p>
<figure class="float">
<a id="Figure-2_002e17"></a>
<object style="width: 26.68ex; height: 26.51ex;" data="fig/chap2/Fig2.17a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.17:</strong> Unbalanced tree produced by adjoining 1 through 7 in sequence.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Exercise-2_002e63"></a>Exercise 2.63:</strong> Each of the following two
procedures converts a binary tree to a list.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tree-</span><span class="pun">&gt;</span><span class="pln">list-1 tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? tree</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">append 
       </span><span class="opn">(</span><span class="pln">tree-</span><span class="pun">&gt;</span><span class="pln">list-1 
        </span><span class="opn">(</span><span class="pln">left-branch tree</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">entry tree</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">tree-</span><span class="pun">&gt;</span><span class="pln">list-1 
              </span><span class="opn">(</span><span class="pln">right-branch tree</span><span class="clo">))))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tree-</span><span class="pun">&gt;</span><span class="pln">list-2 tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">copy-to-list tree result-list</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? tree</span><span class="clo">)</span><span class="pln">
        result-list
        </span><span class="opn">(</span><span class="pln">copy-to-list 
         </span><span class="opn">(</span><span class="pln">left-branch tree</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">entry tree</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">copy-to-list 
                </span><span class="opn">(</span><span class="pln">right-branch tree</span><span class="clo">)</span><span class="pln">
                result-list</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">copy-to-list tree </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span></pre></div>

<ol>
<li> Do the two procedures produce the same result for every tree?  If not, how do
the results differ?  What lists do the two procedures produce for the trees in
<a href="#Figure-2_002e16">Figure 2.16</a>?

</li><li> Do the two procedures have the same order of growth in the number of steps
required to convert a balanced tree with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> elements to a list?  If not,
which one grows more slowly?

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e64"></a>Exercise 2.64:</strong> The following procedure
<code>list-&gt;tree</code> converts an ordered list to a balanced binary tree.  The
helper procedure <code>partial-tree</code> takes as arguments an integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and
list of at least <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> elements and constructs a balanced tree containing the
first <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> elements of the list.  The result returned by <code>partial-tree</code>
is a pair (formed with <code>cons</code>) whose <code>car</code> is the constructed tree
and whose <code>cdr</code> is the list of elements not included in the tree.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list-</span><span class="pun">&gt;</span><span class="pln">tree elements</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="opn">(</span><span class="pln">partial-tree 
        elements </span><span class="opn">(</span><span class="pln">length elements</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">partial-tree elts n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> elts</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">left-size 
             </span><span class="opn">(</span><span class="pln">quotient </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">left-result 
               </span><span class="opn">(</span><span class="pln">partial-tree 
                elts left-size</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">left-tree 
                 </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> left-result</span><span class="clo">))</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">non-left-elts 
                 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> left-result</span><span class="clo">))</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">right-size 
                 </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> left-size </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">this-entry 
                   </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> non-left-elts</span><span class="clo">))</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">right-result 
                   </span><span class="opn">(</span><span class="pln">partial-tree 
                    </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> non-left-elts</span><span class="clo">)</span><span class="pln">
                    right-size</span><span class="clo">)))</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">right-tree 
                     </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> right-result</span><span class="clo">))</span><span class="pln">
                    </span><span class="opn">(</span><span class="pln">remaining-elts 
                     </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> right-result</span><span class="clo">)))</span><span class="pln">
                </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-tree this-entry 
                                 left-tree 
                                 right-tree</span><span class="clo">)</span><span class="pln">
                      remaining-elts</span><span class="clo">))))))))</span></pre></div>

<ol>
<li> Write a short paragraph explaining as clearly as you can how
<code>partial-tree</code> works.  Draw the tree produced by <code>list-&gt;tree</code> for
the list <code>(1 3 5 7 9 11)</code>.

</li><li> What is the order of growth in the number of steps required by
<code>list-&gt;tree</code> to convert a list of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> elements?

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e65"></a>Exercise 2.65:</strong> Use the results of <a href="#Exercise-2_002e63">Exercise 2.63</a> 
and <a href="#Exercise-2_002e64">Exercise 2.64</a> to give <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> implementations of
<code>union-set</code> and <code>intersection-set</code> for sets implemented as (balanced)
binary trees.<a class="footnote_link" id="DOCF107" href="#FOOT107"><sup>107</sup></a>
</p></blockquote>

<a id="Sets-and-information-retrieval"></a>
<h5 class="subsubheading">Sets and information retrieval</h5>

<p>We have examined options for using lists to represent sets and have seen how
the choice of representation for a data object can have a large impact on the
performance of the programs that use the data.  Another reason for
concentrating on sets is that the techniques discussed here appear again and
again in applications involving information retrieval.
</p>
<p>Consider a data base containing a large number of individual records, such as
the personnel files for a company or the transactions in an accounting system.
A typical data-management system spends a large amount of time accessing or
modifying the data in the records and therefore requires an efficient method
for accessing records.  This is done by identifying a part of each record to
serve as an identifying <a id="index-key"></a>
<em>key</em>.  A key can be anything that uniquely
identifies the record.  For a personnel file, it might be an employee’s ID
number.  For an accounting system, it might be a transaction number.  Whatever
the key is, when we define the record as a data structure we should include a
<code>key</code> selector procedure that retrieves the key associated with a given
record.
</p>
<p>Now we represent the data base as a set of records. To locate the record with a
given key we use a procedure <code>lookup</code>, which takes as arguments a key and
a data base and which returns the record that has that key, or false if there
is no such record.  <code>Lookup</code> is implemented in almost the same way as
<code>element-of-set?</code>.  For example, if the set of records is implemented as
an unordered list, we could use
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lookup given-key set-of-records</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? set-of-records</span><span class="clo">)</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">equal</span><span class="pun">?</span><span class="pln"> given-key 
                 </span><span class="opn">(</span><span class="pln">key </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> set-of-records</span><span class="clo">)))</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> set-of-records</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">lookup given-key 
                 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> set-of-records</span><span class="clo">)))))</span></pre></div>

<p>Of course, there are better ways to represent large sets than as unordered
lists.  Information-retrieval systems in which records have to be “randomly
accessed” are typically implemented by a tree-based method, such as the
binary-tree representation discussed previously.  In designing such a system
the methodology of data abstraction can be a great help.  The designer can
create an initial implementation using a simple, straightforward representation
such as unordered lists.  This will be unsuitable for the eventual system, but
it can be useful in providing a “quick and dirty” data base with which to
test the rest of the system.  Later on, the data representation can be modified
to be more sophisticated.  If the data base is accessed in terms of abstract
selectors and constructors, this change in representation will not require any
changes to the rest of the system.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e66"></a>Exercise 2.66:</strong> Implement the <code>lookup</code>
procedure for the case where the set of records is structured as a binary tree,
ordered by the numerical values of the keys.
</p></blockquote>

<a id="g_t2_002e3_002e4"></a>
<a id="Example_003a-Huffman-Encoding-Trees"></a>
<h4 class="subsection"><span class="secnum">2.3.4</span><span class="sectitle">Example: Huffman Encoding Trees</span></h4>

<p>This section provides practice in the use of list structure and data
abstraction to manipulate sets and trees.  The application is to methods for
representing data as sequences of ones and zeros (bits).  For example, the
ASCII standard code used to represent text in computers encodes each character
as a sequence of seven bits.  Using seven bits allows us to distinguish <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mn>2</mn>
    <mn>7</mn>
  </msup>
</math>,
or 128, possible different characters.  In general, if we want to distinguish
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> different symbols, we will need to use <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>log</mi>
      <mn>2</mn>
    </msub>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
  </mrow>
</math> bits per
symbol.  If all our messages are made up of the eight symbols A, B, C, D, E, F,
G, and H, we can choose a code with three bits per character, for example
</p>
<div class="example">
<pre class="example">A 000  C 010  E 100  G 110
B 001  D 011  F 101  H 111
</pre></div>

<p>With this code, the message
</p>
<div class="example">
<pre class="example">BACADAEAFABBAAAGAH
</pre></div>

<p>is encoded as the string of 54 bits
</p>
<div class="example">
<pre class="example">001000010000011000100000101
000001001000000000110000111
</pre></div>

<p>Codes such as ASCII and the A-through-H code above are known as
<a id="index-fixed_002dlength"></a>
<em>fixed-length</em> codes, because they represent each symbol in the message
with the same number of bits.  It is sometimes advantageous to use
<a id="index-variable_002dlength"></a>
<em>variable-length</em> codes, in which different symbols may be represented
by different numbers of bits.  For example, Morse code does not use the same
number of dots and dashes for each letter of the alphabet.  In particular, E,
the most frequent letter, is represented by a single dot.  In general, if our
messages are such that some symbols appear very frequently and some very
rarely, we can encode data more efficiently (i.e., using fewer bits per
message) if we assign shorter codes to the frequent symbols.  Consider the
following alternative code for the letters A through H:
</p>
<div class="example">
<pre class="example">A 0    C 1010  E 1100  G 1110
B 100  D 1011  F 1101  H 1111
</pre></div>

<p>With this code, the same message as above is encoded as the string
</p>
<div class="example">
<pre class="example">100010100101101100011
010100100000111001111
</pre></div>

<p>This string contains 42 bits, so it saves more than 20% in space in comparison
with the fixed-length code shown above.
</p>
<p>One of the difficulties of using a variable-length code is knowing when you
have reached the end of a symbol in reading a sequence of zeros and ones.
Morse code solves this problem by using a special <a id="index-separator-code"></a>
<em>separator code</em> (in
this case, a pause) after the sequence of dots and dashes for each letter.
Another solution is to design the code in such a way that no complete code for
any symbol is the beginning (or <a id="index-prefix"></a>
<em>prefix</em>) of the code for another
symbol.  Such a code is called a <a id="index-prefix-code"></a>
<em>prefix code</em>.  In the example above,
A is encoded by 0 and B is encoded by 100, so no other symbol can have a code
that begins with 0 or with 100.
</p>
<p>In general, we can attain significant savings if we use variable-length prefix
codes that take advantage of the relative frequencies of the symbols in the
messages to be encoded.  One particular scheme for doing this is called the
Huffman encoding method, after its discoverer, David Huffman.  A Huffman code
can be represented as a binary tree whose leaves are the symbols that are
encoded.  At each non-leaf node of the tree there is a set containing all the
symbols in the leaves that lie below the node.  In addition, each symbol at a
leaf is assigned a weight (which is its relative frequency), and each non-leaf
node contains a weight that is the sum of all the weights of the leaves lying
below it.  The weights are not used in the encoding or the decoding process.
We will see below how they are used to help construct the tree.
</p>
<p><a href="#Figure-2_002e18">Figure 2.18</a> shows the Huffman tree for the A-through-H code given above.
The weights at the leaves indicate that the tree was designed for messages in
which A appears with relative frequency 8, B with relative frequency 3, and the
other letters each with relative frequency 1.
</p>
<figure class="float">
<a id="Figure-2_002e18"></a>
<object style="width: 53.01ex; height: 35.23ex;" data="fig/chap2/Fig2.18a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.18:</strong> A Huffman encoding tree.</p>
</figcaption>
</figure>

<p>Given a Huffman tree, we can find the encoding of any symbol by starting at the
root and moving down until we reach the leaf that holds the symbol.  Each time
we move down a left branch we add a 0 to the code, and each time we move down a
right branch we add a 1.  (We decide which branch to follow by testing to see
which branch either is the leaf node for the symbol or contains the symbol in
its set.)  For example, starting from the root of the tree in <a href="#Figure-2_002e18">Figure 2.18</a>, 
we arrive at the leaf for D by following a right branch, then a left
branch, then a right branch, then a right branch; hence, the code for D is
1011.
</p>
<p>To decode a bit sequence using a Huffman tree, we begin at the root and use the
successive zeros and ones of the bit sequence to determine whether to move down
the left or the right branch.  Each time we come to a leaf, we have generated a
new symbol in the message, at which point we start over from the root of the
tree to find the next symbol.  For example, suppose we are given the tree above
and the sequence 10001010.  Starting at the root, we move down the right
branch, (since the first bit of the string is 1), then down the left branch
(since the second bit is 0), then down the left branch (since the third bit is
also 0).  This brings us to the leaf for B, so the first symbol of the decoded
message is B.  Now we start again at the root, and we make a left move because
the next bit in the string is 0.  This brings us to the leaf for A.  Then we
start again at the root with the rest of the string 1010, so we move right,
left, right, left and reach C.  Thus, the entire message is BAC.
</p>
<a id="Generating-Huffman-trees"></a>
<h5 class="subsubheading">Generating Huffman trees</h5>

<p>Given an “alphabet” of symbols and their relative frequencies, how do we
construct the “best” code?  (In other words, which tree will encode messages
with the fewest bits?)  Huffman gave an algorithm for doing this and showed
that the resulting code is indeed the best variable-length code for messages
where the relative frequency of the symbols matches the frequencies with which
the code was constructed.  We will not prove this optimality of Huffman codes
here, but we will show how Huffman trees are constructed.<a class="footnote_link" id="DOCF108" href="#FOOT108"><sup>108</sup></a>
</p>
<p>The algorithm for generating a Huffman tree is very simple. The idea is to
arrange the tree so that the symbols with the lowest frequency appear farthest
away from the root. Begin with the set of leaf nodes, containing symbols and
their frequencies, as determined by the initial data from which the code is to
be constructed. Now find two leaves with the lowest weights and merge them to
produce a node that has these two nodes as its left and right branches. The
weight of the new node is the sum of the two weights. Remove the two leaves
from the original set and replace them by this new node. Now continue this
process. At each step, merge two nodes with the smallest weights, removing them
from the set and replacing them with a node that has these two as its left and
right branches. The process stops when there is only one node left, which is
the root of the entire tree.  Here is how the Huffman tree of <a href="#Figure-2_002e18">Figure 2.18</a>
was generated:
</p>
<div class="example">
<pre class="example">Initial {(A 8) (B 3) (C 1) (D 1) 
leaves   (E 1) (F 1) (G 1) (H 1)}

Merge   {(A 8) (B 3) ({C D} 2) 
         (E 1) (F 1) (G 1) (H 1)}

Merge   {(A 8) (B 3) ({C D} 2) 
         ({E F} 2) (G 1) (H 1)}

Merge   {(A 8) (B 3) ({C D} 2) 
         ({E F} 2) ({G H} 2)}

Merge   {(A 8) (B 3) ({C D} 2) 
         ({E F G H} 4)}

Merge   {(A 8) ({B C D} 5) 
         ({E F G H} 4)}

Merge   {(A 8) ({B C D E F G H} 9)}

Final   {({A B C D E F G H} 17)}
merge    
</pre></div>

<p>The algorithm does not always specify a unique tree, because there may not be
unique smallest-weight nodes at each step.  Also, the choice of the order in
which the two nodes are merged (i.e., which will be the right branch and which
will be the left branch) is arbitrary.
</p>
<a id="Representing-Huffman-trees"></a>
<h5 class="subsubheading">Representing Huffman trees</h5>

<p>In the exercises below we will work with a system that uses Huffman trees to
encode and decode messages and generates Huffman trees according to the
algorithm outlined above.  We will begin by discussing how trees are
represented.
</p>
<p>Leaves of the tree are represented by a list consisting of the symbol
<code>leaf</code>, the symbol at the leaf, and the weight:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-leaf symbol weight</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'leaf</span><span class="pln"> symbol weight</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">leaf? object</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> object</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'leaf</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol-leaf x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">weight-leaf x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> x</span><span class="clo">))</span></pre></div>

<p>A general tree will be a list of a left branch, a right branch, a set of
symbols, and a weight.  The set of symbols will be simply a list of the
symbols, rather than some more sophisticated set representation.  When we make
a tree by merging two nodes, we obtain the weight of the tree as the sum of the
weights of the nodes, and the set of symbols as the union of the sets of
symbols for the nodes.  Since our symbol sets are represented as lists, we can
form the union by using the <code>append</code> procedure we defined in 
<a href="2_002e2.xhtml#g_t2_002e2_002e1">2.2.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-code-tree left right</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list left
        right
        </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="pln">symbols left</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">symbols right</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">weight left</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">weight right</span><span class="clo">))))</span></pre></div>

<p>If we make a tree in this way, we have the following selectors:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">left-branch tree</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">right-branch tree</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbols tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">leaf? tree</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">symbol-leaf tree</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> tree</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">weight tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">leaf? tree</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">weight-leaf tree</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cadddr</span><span class="pln"> tree</span><span class="clo">)))</span></pre></div>

<p>The procedures <code>symbols</code> and <code>weight</code> must do something slightly
different depending on whether they are called with a leaf or a general tree.
These are simple examples of <a id="index-generic-procedures"></a>
<em>generic procedures</em> (procedures that can
handle more than one kind of data), which we will have much more to say about
in <a href="2_002e4.xhtml#g_t2_002e4">2.4</a> and <a href="2_002e5.xhtml#g_t2_002e5">2.5</a>.
</p>
<a id="The-decoding-procedure"></a>
<h5 class="subsubheading">The decoding procedure</h5>

<p>The following procedure implements the decoding algorithm.  It takes as
arguments a list of zeros and ones, together with a Huffman tree.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">decode bits tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">decode-1 bits current-branch</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? bits</span><span class="clo">)</span><span class="pln">
        </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">next-branch
               </span><span class="opn">(</span><span class="pln">choose-branch 
                </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> bits</span><span class="clo">)</span><span class="pln"> 
                current-branch</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">leaf? next-branch</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">symbol-leaf next-branch</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">decode-1 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> bits</span><span class="clo">)</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">decode-1 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> bits</span><span class="clo">)</span><span class="pln"> 
                        next-branch</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">decode-1 bits tree</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">choose-branch bit branch</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> bit </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">left-branch branch</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> bit </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">right-branch branch</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"bad bit: 
               CHOOSE-BRANCH"</span><span class="pln"> bit</span><span class="clo">))))</span></pre></div>

<p>The procedure <code>decode-1</code> takes two arguments: the list of remaining bits
and the current position in the tree.  It keeps moving “down” the tree,
choosing a left or a right branch according to whether the next bit in the list
is a zero or a one.  (This is done with the procedure <code>choose-branch</code>.)
When it reaches a leaf, it returns the symbol at that leaf as the next symbol
in the message by <code>cons</code>ing it onto the result of decoding the rest of the
message, starting at the root of the tree.  Note the error check in the final
clause of <code>choose-branch</code>, which complains if the procedure finds
something other than a zero or a one in the input data.
</p>
<a id="Sets-of-weighted-elements"></a>
<h5 class="subsubheading">Sets of weighted elements</h5>

<p>In our representation of trees, each non-leaf node contains a set of symbols,
which we have represented as a simple list.  However, the tree-generating
algorithm discussed above requires that we also work with sets of leaves and
trees, successively merging the two smallest items.  Since we will be required
to repeatedly find the smallest item in a set, it is convenient to use an
ordered representation for this kind of set.
</p>
<p>We will represent a set of leaves and trees as a list of elements, arranged in
increasing order of weight.  The following <code>adjoin-set</code> procedure for
constructing sets is similar to the one described in <a href="#Exercise-2_002e61">Exercise 2.61</a>;
however, items are compared by their weights, and the element being added to
the set is never already in it.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">adjoin-set x </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? </span><span class="kwd">set</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list x</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">weight x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">weight </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">)))</span><span class="pln"> 
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x </span><span class="kwd">set</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">adjoin-set x </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> </span><span class="kwd">set</span><span class="clo">))))))</span></pre></div>

<p>The following procedure takes a list of symbol-frequency pairs such as
<code>((A 4) (B 2) (C 1) (D 1))</code> and constructs an initial ordered set of
leaves, ready to be merged according to the Huffman algorithm:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-leaf-set pairs</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? pairs</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">pair </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pairs</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">adjoin-set 
         </span><span class="opn">(</span><span class="pln">make-leaf </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pair</span><span class="clo">)</span><span class="pln">    </span><span class="roman"><span class="com">; symbol</span></span><span class="pln">
                    </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> pair</span><span class="clo">))</span><span class="pln">  </span><span class="roman"><span class="com">; frequency</span></span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-leaf-set </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> pairs</span><span class="clo">))))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-2_002e67"></a>Exercise 2.67:</strong> Define an encoding tree and a
sample message:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> sample-tree
  </span><span class="opn">(</span><span class="pln">make-code-tree 
   </span><span class="opn">(</span><span class="pln">make-leaf </span><span class="lit">'A</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">make-code-tree
    </span><span class="opn">(</span><span class="pln">make-leaf </span><span class="lit">'B</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-code-tree 
     </span><span class="opn">(</span><span class="pln">make-leaf </span><span class="lit">'D</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">make-leaf </span><span class="lit">'C</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> sample-message 
  </span><span class="lit">'</span><span class="opn">(</span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>Use the <code>decode</code> procedure to decode the message, and give the result.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e68"></a>Exercise 2.68:</strong> The <code>encode</code> procedure takes
as arguments a message and a tree and produces the list of bits that gives the
encoded message.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">encode message tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? message</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">append 
       </span><span class="opn">(</span><span class="pln">encode-symbol </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> message</span><span class="clo">)</span><span class="pln"> 
                      tree</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">encode </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> message</span><span class="clo">)</span><span class="pln"> tree</span><span class="clo">))))</span></pre></div>

<p><code>Encode-symbol</code> is a procedure, which you must write, that returns the
list of bits that encodes a given symbol according to a given tree.  You should
design <code>encode-symbol</code> so that it signals an error if the symbol is not in
the tree at all.  Test your procedure by encoding the result you obtained in
<a href="#Exercise-2_002e67">Exercise 2.67</a> with the sample tree and seeing whether it is the same as
the original sample message.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e69"></a>Exercise 2.69:</strong> The following procedure takes as
its argument a list of symbol-frequency pairs (where no symbol appears in more
than one pair) and generates a Huffman encoding tree according to the Huffman
algorithm.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">generate-huffman-tree pairs</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">successive-merge 
   </span><span class="opn">(</span><span class="pln">make-leaf-set pairs</span><span class="clo">)))</span></pre></div>

<p><code>Make-leaf-set</code> is the procedure given above that transforms the list of
pairs into an ordered set of leaves.  <code>Successive-merge</code> is the procedure
you must write, using <code>make-code-tree</code> to successively merge the
smallest-weight elements of the set until there is only one element left, which
is the desired Huffman tree.  (This procedure is slightly tricky, but not
really complicated.  If you find yourself designing a complex procedure, then
you are almost certainly doing something wrong.  You can take significant
advantage of the fact that we are using an ordered set representation.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e70"></a>Exercise 2.70:</strong> The following eight-symbol
alphabet with associated relative frequencies was designed to efficiently
encode the lyrics of 1950s rock songs.  (Note that the “symbols” of an
“alphabet” need not be individual letters.)
</p>
<div class="example">
<pre class="example">
A    2    NA  16
BOOM 1    SHA  3
GET  2    YIP  9
JOB  2    WAH  1
</pre></div>

<p>Use <code>generate-huffman-tree</code> (<a href="#Exercise-2_002e69">Exercise 2.69</a>) to generate a
corresponding Huffman tree, and use <code>encode</code> (<a href="#Exercise-2_002e68">Exercise 2.68</a>) to
encode the following message:
</p>
<div class="example">
<pre class="example">Get a job
Sha na na na na na na na na

Get a job
Sha na na na na na na na na

Wah yip yip yip yip 
yip yip yip yip yip
Sha boom
</pre></div>

<p>How many bits are required for the encoding?  What is the smallest number of
bits that would be needed to encode this song if we used a fixed-length code
for the eight-symbol alphabet?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e71"></a>Exercise 2.71:</strong> Suppose we have a Huffman tree
for an alphabet of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> symbols, and that the relative frequencies of the
symbols are <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>,</mo>
    <mn>2</mn>
    <mo>,</mo>
    <mn>4</mn>
    <mo>,</mo>
    <mo>…<!-- … --></mo>
    <mo>,</mo>
    <msup>
      <mn>2</mn>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msup>
  </mrow>
</math>.  Sketch the tree for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>=</mo>
    <mn>5</mn>
  </mrow>
</math>; for
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>=</mo>
    <mn>10</mn>
  </mrow>
</math>.  In such a tree (for general <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>) how many bits are required to
encode the most frequent symbol?  The least frequent symbol?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e72"></a>Exercise 2.72:</strong> Consider the encoding procedure
that you designed in <a href="#Exercise-2_002e68">Exercise 2.68</a>.  What is the order of growth in the
number of steps needed to encode a symbol?  Be sure to include the number of
steps needed to search the symbol list at each node encountered.  To answer
this question in general is difficult.  Consider the special case where the
relative frequencies of the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> symbols are as described in <a href="#Exercise-2_002e71">Exercise 2.71</a>, 
and give the order of growth (as a function of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>) of the number of
steps needed to encode the most frequent and least frequent symbols in the
alphabet.
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT98"><p><a class="footnote_backlink" href="#DOCF98"><sup>98</sup></a>
Allowing quotation in a language wreaks havoc
with the ability to reason about the language in simple terms, because it
destroys the notion that equals can be substituted for equals.  For example,
three is one plus two, but the word “three” is not the phrase “one plus
two.”  Quotation is powerful because it gives us a way to build expressions
that manipulate other expressions (as we will see when we write an interpreter
in <a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a>). But allowing statements in a language that talk about
other statements in that language makes it very difficult to maintain any
coherent principle of what “equals can be substituted for equals” should
mean.  For example, if we know that the evening star is the morning star, then
from the statement “the evening star is Venus” we can deduce “the morning
star is Venus.”  However, given that “John knows that the evening star is
Venus” we cannot infer that “John knows that the morning star is Venus.”</p>
</div>
<div id="FOOT99"><p><a class="footnote_backlink" href="#DOCF99"><sup>99</sup></a>
The
single quote is different from the double quote we have been using to enclose
character strings to be printed.  Whereas the single quote can be used to
denote lists or symbols, the double quote is used only with character strings.
In this book, the only use for character strings is as items to be printed.</p>
</div>
<div id="FOOT100"><p><a class="footnote_backlink" href="#DOCF100"><sup>100</sup></a>
Strictly, our use of the quotation
mark violates the general rule that all compound expressions in our language
should be delimited by parentheses and look like lists.  We can recover this
consistency by introducing a special form <code>quote</code>, which serves the same
purpose as the quotation mark.  Thus, we would type <code>(quote a)</code> instead of
<code>'a</code>, and we would type <code>(quote (a b c))</code> instead of <code>'(a b c)</code>.
This is precisely how the interpreter works.  The quotation mark is just a
single-character abbreviation for wrapping the next complete expression with
<code>quote</code> to form <code>(quote ⟨<var>expression</var>⟩)</code>.  This is
important because it maintains the principle that any expression seen by the
interpreter can be manipulated as a data object.  For instance, we could
construct the expression <code>(car '(a b c))</code>, which is the same as <code>(car
(quote (a b c)))</code>, by evaluating <code>(list 'car (list 'quote '(a b c)))</code>.</p>
</div>
<div id="FOOT101"><p><a class="footnote_backlink" href="#DOCF101"><sup>101</sup></a>
We
can consider two symbols to be “the same” if they consist of the same
characters in the same order.  Such a definition skirts a deep issue that we
are not yet ready to address: the meaning of “sameness” in a programming
language.  We will return to this in <a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a> (<a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a>).</p>
</div>
<div id="FOOT102"><p><a class="footnote_backlink" href="#DOCF102"><sup>102</sup></a>
In practice,
programmers use <code>equal?</code> to compare lists that contain numbers as well as
symbols.  Numbers are not considered to be symbols.  The question of whether
two numerically equal numbers (as tested by <code>=</code>) are also <code>eq?</code> is
highly implementation-dependent.  A better definition of <code>equal?</code> (such as
the one that comes as a primitive in Scheme) would also stipulate that if
<code>a</code> and <code>b</code> are both numbers, then <code>a</code> and <code>b</code> are
<code>equal?</code> if they are numerically equal.</p>
</div>
<div id="FOOT103"><p><a class="footnote_backlink" href="#DOCF103"><sup>103</sup></a>
If we want to be more formal, we can
specify “consistent with the interpretations given above” to mean that the
operations satisfy a collection of rules such as these:
</p>
<ul>
<li> For any set <code>S</code> and any object <code>x</code>,
<code>(element-of-set? x (adjoin-set x S))</code>
is true (informally: “Adjoining an object to a
set produces a set that contains the object”).

</li><li> For any sets <code>S</code> and <code>T</code> and any object <code>x</code>,
<code>(element-of-set? x (union-set S T))</code>
is equal to
<code>(or (element-of-set? x S) (element-of-set? x T))</code>
(informally: “The elements of <code>(union S T)</code> are the elements that
are in <code>S</code> or in <code>T</code>”).

</li><li> For any object <code>x</code>,
<code>(element-of-set? x '())</code>
is false (informally: “No object is an element of the empty set”).

</li></ul>
</div>
<div id="FOOT104"><p><a class="footnote_backlink" href="#DOCF104"><sup>104</sup></a>
Halving the size of the problem at each
step is the distinguishing characteristic of logarithmic growth, as we saw with
the fast-exponentiation algorithm of <a href="1_002e2.xhtml#g_t1_002e2_002e4">1.2.4</a> and the half-interval
search method of <a href="1_002e3.xhtml#g_t1_002e3_002e3">1.3.3</a>.</p>
</div>
<div id="FOOT105"><p><a class="footnote_backlink" href="#DOCF105"><sup>105</sup></a>
We are representing sets in terms of trees, and trees in
terms of lists—in effect, a data abstraction built upon a data abstraction.
We can regard the procedures <code>entry</code>, <code>left-branch</code>,
<code>right-branch</code>, and <code>make-tree</code> as a way of isolating the abstraction
of a “binary tree” from the particular way we might wish to represent such a
tree in terms of list structure.</p>
</div>
<div id="FOOT106"><p><a class="footnote_backlink" href="#DOCF106"><sup>106</sup></a>
Examples of such structures include <a id="index-B_002dtrees"></a>
<em>B-trees</em> and
<a id="index-red_002dblack-trees"></a>
<em>red-black trees</em>.  There is a large literature on data structures
devoted to this problem.  See <a href="References.xhtml#Cormen-et-al_002e-1990">Cormen et al. 1990</a>.</p>
</div>
<div id="FOOT107"><p><a class="footnote_backlink" href="#DOCF107"><sup>107</sup></a>
<a href="#Exercise-2_002e63">Exercise 2.63</a> through <a href="#Exercise-2_002e65">Exercise 2.65</a> are due
to Paul Hilfinger.</p>
</div>
<div id="FOOT108"><p><a class="footnote_backlink" href="#DOCF108"><sup>108</sup></a>
See <a href="References.xhtml#Hamming-1980">Hamming 1980</a> 
for a discussion of the mathematical properties of Huffman codes.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="2_002e4.xhtml#g_t2_002e4" accesskey="n" rel="next">2.4</a>, Prev: <a href="2_002e2.xhtml#g_t2_002e2" accesskey="p" rel="prev">2.2</a>, Up: <a href="#g_t2_002e3" accesskey="u" rel="prev">2.3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>